[1/3] La cryptographie post-quantique

La menace des ordinateurs quantiques pour la cryptographie traditionnelle

 

Introduction à l’informatique quantique

 

L’informatique traditionnelle repose sur un système binaire, dans lequel le bit, prenant la valeur 0 ou 1, est la plus petite unité d’information traitée par un ordinateur. Dans l’informatique quantique, l’unité fondamentale est le qubit qui peut prendre tout un ensemble d’états entre 0 et 1, ces états pouvant être liés entre eux à l’échelle de plusieurs qubits. Ces caractéristiques peuvent, dans certains cas, permettre de réaliser des calculs plus rapides que les bits classiques, en traitant en parallèle plusieurs valeurs possibles. À terme, un ordinateur quantique[1] pourrait effectuer des calculs que les ordinateurs traditionnels ne pourront jamais accomplir en un temps raisonnable.

 

De nombreux travaux sur le calcul quantique sont menés depuis plusieurs décennies (notamment par IBM, Google ou encore Microsoft) et l’écosystème est très dynamique. En France, le Président de la République a présenté en janvier 2021 un plan d'investissement dans les technologies quantiques de 1,8 milliard d'euros sur cinq ans. Diverses technologies de construction d’ordinateurs quantiques existent mais ne permettent encore que des calculs très limités. Cependant, les progrès sont rapides : plusieurs acteurs dont IBM, notamment, ainsi que des startups, comme les entreprises françaises Pasqal, Alice & Bob et Quandela, développent des prototypes d’ordinateurs quantiques de plus en plus sophistiqués.

 

Toutefois, la communauté en sécurité informatique s’inquiète des conséquences que pourrait avoir le calcul quantique sur la cryptographie. En effet, on sait depuis 1994 qu’un ordinateur quantique permettrait de casser la plupart des algorithmes cryptographiques actuellement utilisés. Ce qui était jusqu’à récemment une menace purement théorique devient depuis une dizaine d’années une menace plus sérieuse avec le développement des premiers ordinateurs quantique. Cela s’applique principalement aux mécanismes asymétriques, mais également (dans une moindre mesure) aux mécanismes symétriques, qu’il s’agisse des techniques de chiffrement, de hachage ou de signature électronique.

 

La menace plus ou moins proche des ordinateurs quantiques

 

Ainsi, ce qui est considéré comme sûr aujourd’hui pourrait être compromis avec l’avènement de calculateurs quantiques de capacité suffisante. Il est difficile de prévoir si et quand l’ordinateur quantique atteindra un jour la puissance nécessaire. Cela se compte probablement en décennies. Néanmoins, cette menace incite déjà les chercheurs en cryptographie (dont font partie certains des experts auditionnés) à anticiper les défis posés par l’ordinateur quantique. Cette anticipation est motivée par deux raisons principales :

• les conséquences très sérieuses des attaques  potentielles (voir ci-dessous) et ;
• le constat que l’industrie met souvent du temps à réagir face aux nouvelles technologies, ce qui impose de s’y préparer le plus tôt possible.

 

Concrètement, l’ANSSI a identifié les menaces particulières que font peser l’ordinateur quantique et les algorithmes quantiques sur la sécurité actuelle des données :

• les attaques rétroactives qui consistent à stocker aujourd’hui des données qui transitent chiffrées dans l’attente de pouvoir les déchiffrer facilement un jour (« store now, decrypt later ») ;
• les attaques de contrefaçon de signatures électroniques qui permettent d’usurper l’identité du signataire.

Les attaques quantiques les mieux connues reposent sur des algorithmes spécifiques qui permettent théoriquement de résoudre des problèmes calculatoires qualifiés de « difficiles » (par exemple, la factorisation pour RSA ou le logarithme discret pour l’échange de clés Diffie-Hellman) et que les ordinateurs traditionnels ne peuvent pas résoudre en temps raisonnable :

• l’algorithme quantique de Shor qui menace les systèmes de cryptographie à clé publique les plus utilisés actuellement, et qui résout le problème du logarithme discret (Diffie-Hellman, DSA) et le problème de la factorisation des entiers (RSA) en un temps rapide avec un ordinateur quantique de taille suffisante (même si cette taille est pour l’instant hors de portée des technologies actuelles) ;
• l’algorithme quantique de Grover qui affecte la sécurité des systèmes de cryptographie symétrique, et qui offre  une accélération dite « quadratique » (c’est-à-dire assez modérée, mais suffisante en théorie pour des adversaires assez puissants) pour résoudre le problème de recherche de la clé secrète.

Dans le cas des attaques quantiques sur les cryptosystèmes symétriques, l’impact d’un ordinateur quantique est généralement limité. En effet, il suffira de doubler la taille des clés et d’adapter légèrement le dimensionnement des fonctions de hachage pour revenir à un niveau de sécurité équivalent face à un ordinateur classique.

 

Pour les cryptosystèmes à clé publique, l’impact est bien plus grave. L’une des pistes principales repose sur le remplacement des mécanismes asymétriques actuels par de nouveaux mécanismes résistants aux attaques quantiques : la cryptographie dite post-quantique.

 

La cryptographie post-quantique

 

L’objectif de la cryptographie post-quantique est donc de développer une cryptographie résistante aussi bien aux ordinateurs quantiques qu’aux ordinateurs classiques, tout en permettant de fonctionner sur les architectures et protocoles existants (comme TLS, un protocole de communication sécurisée utilisé sur le web). Autrement dit, la cryptographie post-quantique n’est pas quantique.  

 

Le National Institute of Standards and Technologies (NIST) a lancé en 2016 une campagne internationale d’appels à propositions d’algorithmes en vue de standardiser une nouvelle famille d’algorithmes cryptographiques résistants aux attaques quantiques. Les entretiens ont eu lieu quelques jours ou semaines après la publication par le NIST des quatre premiers algorithmes retenus : l’un concerne l’établissement de clés (pour le chiffrement) et les trois autres les signatures électroniques (pour l’authentification). Plusieurs des algorithmes sélectionnés comptent des chercheurs français parmi leurs auteurs. Les premiers projets de standards basés sur les quatre algorithmes ont été publiés en août 2023 pour consultation publique. D’autres algorithmes sont toujours en processus de sélection. En effet, l'objectif du NIST, et plus généralement de la communauté, est de mettre à disposition de l’industrie, à moyen terme, plusieurs standards adaptés aux contraintes de chaque domaine. Cela permettra de garantir l’existence de solutions alternatives en cas de compromission d’un des standards.

 

Les candidats à la standardisation ont suivi généralement la même approche : construire des primitives cryptographiques à partir de problèmes calculatoires que l’ordinateur quantique ne peut pas résoudre efficacement.  Ces problèmes sont généralement répartis en plusieurs familles : 

 

• La cryptographie fondée sur les réseaux euclidiens repose sur le problème de recherche des plus courts vecteurs dans un réseau de points régulièrement espacés dans un espace mathématique multidimensionnel C’est une approche largement étudiée dans le milieu académique depuis 2005 et qui est également utilisée pour le chiffrement homomorphe. Sur les quatre algorithmes retenus par le NIST, trois reposent sur cette approche.

 

• La cryptographie fondée sur les codes correcteurs d’erreurs repose sur le problème de décodage d’un code correcteur pseudo-aléatoire C’est également une approche éprouvée dont l’étude a commencée dans les années 1970. Parmi les algorithmes encore en lice pour être normalisés, certains reposent sur ce problème mathématique.

 

• La cryptographie fondée sur les fonctions de hachage repose sur le problème d’inversion d’une fonction de hachage. Cette approche est très mature et considérée par les experts comme très sûre mais n’est pertinente que pour la construction de signatures électroniques et est généralement assez peu performante.

 

• La cryptographie fondée sur les isogénies entre courbes elliptiques repose sur le problème de recherche d’une telle isogénie (pour faire simple, une isogénie est une fonction particulière reliant deux courbes elliptiques qui conserve leurs propriétés clés). Cette approche est la plus récente comparée aux autres (une dizaine d’années) mais prometteuse. Parmi les algorithmes candidats, celui qui reposait sur cette cryptographie a été cassé. Les experts auditionnés pensent que l’étude de cette approche mérite d’être poursuivie du fait de la faible taille des clés, bien qu’elle souffre encore d’un manque de maturité et de la puissance de calcul nécessaire pour chiffrer. Elle peut être adaptée à certaines applications qui sont davantage contraintes par le volume de données échangées.

 

• La cryptographie fondée sur les polynômes multivariés repose principalement sur des problèmes de résolution de systèmes d’équations polynomiales multivariées. Cette approche remonte aux années 1980. Même si le schéma de base reste sécurisé, de nombreux mécanismes basés sur cette technique ont été cassés. Certains mécanismes multivariés pourraient néanmoins rester pertinents, notamment pour les signatures électroniques.

 

La migration en douceur vers le post-quantique

 

L’ANSSI a commenté la décision du NIST concernant les premiers algorithmes choisis pour la standardisation d'algorithmes cryptographiques post-quantiques. Bien que satisfaite sur le plan scientifique, l'ANSSI ne souhaite pas le remplacement immédiat des algorithmes asymétriques actuels par des algorithmes post-quantiques. Dans la mesure où ces algorithmes sont récents, l’ANSSI préconise de les utiliser  de manière hybride, c’est-à-dire en les combinant avec les algorithmes pré-quantiques reconnus et éprouvés (comme le chiffrement RSA et la cryptographie basée sur les courbes elliptiques), de manière à garantir une sécurité au moins équivalente à chacun des deux mécanismes utilisés. Ceci permet d’assurer une protection à long terme contre le calcul quantique tout en empêchant toute régression de sécurité. L’agence recommande un déploiement du post-quantique en trois phases.

• Dès maintenant : l’hybridation du post-quantique avec la cryptographie classique pour certains cas d’usage spécifiques (données particulièrement sensibles ou produit qui ne pourra pas être mis à jour d’ici 2030 par exemple) ;
• Dans un deuxième temps (à partir de 2025 environ) : la mise en place possible d’algorithmes post-quantiques, toujours en mode hybride, et est vivement recommandée dès qu’une sécurité à long terme est recherchée (l’ANSSI pourra donner un avis plus tranché sur le post-quantique et des recommandations sur comment hybrider) ;
• Vers 2030 : utilisation d’algorithmes post-quantiques seuls, sans hybridation, s’ils sont reconnus sûrs.

D’autres agences de sécurité européennes partagent la même position et adoptent des recommandations très similaires à celles de l’ANSSI, notamment en termes d’hybridation.

 

Par exception à la règle générale, les mécanismes de signature basés sur les fonctions de hachage, connus et étudiés depuis longtemps, sont dès maintenant considérés comme sûrs et peuvent donc être utilisés sans hybridation. Cependant, ces algorithmes sont peu performants (notamment en termes de taille de signature) et leur emploi en pratique est restreint à certains cas d’usage spécifiques.

 

Conclusion

 

La menace potentielle que représentent les ordinateurs quantiques sur les systèmes cryptographiques actuels a été clairement mise en lumière au cours des entretiens. Cette épée de Damoclès suscite des efforts conséquents pour développer des solutions résistantes, à travers la cryptographie post-quantique. Les travaux du NIST pour standardiser les algorithmes post-quantiques marquent une étape cruciale dans cette évolution.

 

Cependant, la nécessité d'une transition graduelle vers ces systèmes, comme recommandée par l'ANSSI, souligne l'importance d’adopter une approche prudente et bien pensée pour le déploiement du post-quantique. Si certains acteurs manipulant des informations nécessitant une protection de longue durée doivent commencer dès aujourd’hui à se préoccuper de cette migration vers le post-quantique, les autres peuvent encore attendre quelques années que l’ANSSI produise des recommandations à leur destination, bien qu’il soit possible d’anticiper ces changements, en particulier en favorisant la « cryptoagilité ».

 

La sécurisation des données personnelles repose largement sur le recours à des systèmes cryptographiques sûrs, dont la CNIL recommande depuis longtemps l’utilisation dans de nombreux contextes. La possibilité de l’émergence d’ordinateurs quantiques puissants, d’ici quelques dizaines d’années, oblige non seulement à penser les technologies qui seront sûres dans ce nouveau contexte mais à l’anticiper dès à présent, dans la mesure où il n’est aujourd’hui plus possible de sécuriser des données personnelles durablement sans tenir compte de cette évolution vraisemblable.

 

 

[1] On parle ici « d’ordinateur quantique » dans le sens d’un calculateur capable d’effectuer des calculs quantiques de grande échelle, le cas échéant sur un nombre limité de tâches spécialisées, non pas comme d’un équivalent quantique d’un ordinateur « classique ».

 

 

 

---

 

Illustration : Flickr